package chapter03_binaryTree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 描述：
 *  序列化与反序列化二叉树
 * @author hl
 * @date 2021/5/3 13:13
 */
public class SerialBinaryTree {
    public static void main(String[] args) {
        Node node = new Node(1);
        node.left = new Node(2);
        node.left.left = new Node(4);
        node.left.left.right = new Node(7);
        node.right = new Node(3);
        node.right.left = new Node(5);
        node.right.right = new Node(6);
        SerialBinaryTree instance = new SerialBinaryTree();
        String str = instance.serialByLevel(node);
        System.out.println(str);
        Node head = instance.reconByLevel(str);
        System.out.println(head);
    }
    public String serialByLevel(Node head){
        if (head == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        Node cur = null;
        StringBuilder res = new StringBuilder();
        res.append(head.val + "!");
        while (!queue.isEmpty()) {
            cur = queue.poll();
            if(cur.left != null){
                res.append(cur.left.val + "!");
                queue.offer(cur.left);
            }else{
                res.append("#!");
            }
            if (cur.right != null) {
                res.append(cur.right.val + "!");
                queue.offer(cur.right);
            }else{
                res.append("#!");
            }
        }
        return res.toString();
    }

    public Node reconByLevel(String levelStr){
        String[] els = levelStr.split("!");
        Queue<Node> queue = new LinkedList<>();
        Node head = generateNode(els[0]);
        if (head == null) {
            return null;
        }
        queue.offer(head);
        Node cur = null;
        int index = 1;
        while(!queue.isEmpty()){
            cur = queue.poll();
            cur.left = generateNode(els[index++]);
            cur.right = generateNode(els[index++]);
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        return head;
    }

    private Node generateNode(String value) {
        if (!value.equals("#")) {
            return new Node(Integer.parseInt(value));
        }
        return null;
    }


    /**
     * 层序遍历序列化二叉树
     * @param head
     * @return
     */
    public String serialByLevel2(Node head){
        if (head == null) {
            return null;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(head);
        Node cur = null;
        Node left = null;
        Node right = null;
        StringBuilder res = new StringBuilder();
        int n ;
        while(!queue.isEmpty()){
            n = queue.size();
            for (int i = 0; i < n; i++) {
                cur = queue.poll();
                res.append(cur != null ? cur.val + "!" : "#!");
                if (cur != null) {
                    left = cur.left;
                    right = cur.right;
                    queue.offer(left);
                    queue.offer(right);
                }
                if(i == n - 1){
                    res.append("-");
                }
            }
        }
        return res.toString();
    }
    public Node unSerialByLevel2(String levelStr){
        if ("".equals(levelStr)) {
            return null;
        }
        String[] level = levelStr.split("-");
        Queue<Node> queue = new LinkedList<>();
        String[] el = null;
        Node cur = null;
        Node head = null;
        Node p = null;
        for (int i = 0; i < level.length; i++) {
            el = level[i].split("!");
            for (int j = 0; j < el.length; j++) {
                cur = el[j].equals("#") ? null : new Node(Integer.parseInt(el[j]));
                if (i == 0 && j == 0) {
                    head = cur;
                }
                queue.offer(cur);
                p = queue.peek();
                if (i > 0 && p != null) {
                    if (j % 2 == 0) {
                        p.left = cur;
                    }else{
                        p.right = cur;
                        queue.poll();
                    }
                }
            }

        }
        return head;
    }
}
